import random
import itertools
import sys
import csv
from functools import reduce

# 训练部分
param_value_map = [""]  # 将各个参数的值映射到整数，方便计算

test_case = []
test_case_val_size = []  # 记录每个参数的值的数量，用于计算N,这样遍历时时间换空间
AETG_covering_array = []

max_val_num = 0
expected_tway_num = 0
covered_tway_combination_set = set()

# 参数部分
cover_strength = 2  # 测试用例的覆盖方式，即t，默认pair-wise
candidate_size = 50  # candidate数量，即M
input_file = 'test.csv'
directory_identifier = '目录'

# 用于迭代的全局变量
shuffled_test_case_idx, candidate_row, candidate_covering_combs_num = [], [], 0
# t,k,v
"""
t : t-way
k : k params
v : max value number

"""


def Combination(n, m):
    """
    :return: 返回组合数C(n,m)
    """
    Min = min(m, n - m)
    result = 1

    for i in range(0, Min):
        result = result * (n - i) / (Min - i)
    return int(result)


def Factorial(n):
    if n == 0 or n == 1:
        return 1
    else:
        return n * Factorial(n - 1)


def load_test_case_file(file_path):
    """
    读取数据文件
    :param file_path: 文件路径
    """
    global max_val_num
    with open(file_path) as f:
        i = 0
        dir_col_num = 0

        for row_arr in csv.reader(f.readlines()):

            if i == 0:  # 首先根据标识符判断目录列数
                i += 1
                for cell in row_arr:
                    if cell == directory_identifier:
                        dir_col_num += 1
                    else:
                        break
            else:

                val_list = []
                for val_cell in filter(lambda item: len(item) > 0, row_arr[dir_col_num:]):  # 取非0块，即有意义的选项
                    param_value_map.append(val_cell)
                    val_list.append(i)
                    i += 1
                if len(val_list) == 0:
                    continue
                if len(val_list) > max_val_num:  # 更新v的值
                    max_val_num = len(val_list)
                test_case.append(val_list)
                test_case_val_size.append(len(val_list))


def generate_required_tway_num():
    """
    根据测试数据获得期望的t-way combination的数量
    :return:
    """
    global expected_tway_num
    rst = list(itertools.combinations(test_case_val_size, cover_strength))  # 计算t种组合方法
    for item in rst:
        expected_tway_num += reduce(lambda a, b: a * b, item)


def AETG(N, t, k):
    global shuffled_test_case_idx, candidate_row, candidate_covering_combs_num

    while N > 0:
        inverted_candidates_dict = {}  # 是K(cover数量):V(covering_array)结构的字典
        best_covering_num = 0
        for j in range(candidate_size):
            shuffled_test_case_idx = list(range(k))
            random.shuffle(shuffled_test_case_idx)  # 打乱队列
            candidate_row = []  # 在当前随机序列下生成的covering array，将被添加进inverted_candidates_dict
            candidate_covering_combs_num = 0  # 记录一个选择好的covering array能cover的comb数量

            best_covering_num = aetg_iter(inverted_candidates_dict, k, t, 0)
            if best_covering_num == Combination(k, t):
                break

        best_covering_num = max(inverted_candidates_dict.keys())
        best_covering_array = inverted_candidates_dict[best_covering_num]
        AETG_covering_array.append(best_covering_array)

        for comb in itertools.combinations(best_covering_array, t):
            covered_tway_combination_set.add(tuple(sorted(comb)))  # 添加的时候不能忘了排好序

        N -= best_covering_num
        # 输出选取covering array之后的信息
        print("selected CA:", best_covering_array, ", covering {} {}way-combinations".format(best_covering_num,cover_strength), "N is ", N)


def aetg_iter(inverted_candidates_dict, k, t, start):
    global shuffled_test_case_idx, candidate_row, candidate_covering_combs_num

    if start + 1 < t:
        best_covered_num = 0
        for val in test_case[shuffled_test_case_idx[start]]:
            candidate_row.append(val)
            best_covered_num = max(best_covered_num, aetg_iter(inverted_candidates_dict, k, t, start + 1))
            candidate_row = candidate_row[:start]
            return best_covered_num

    else:
        optimal_val = 0
        for i in range(start, k):
            covered_combs_num = 0  # 记录最优val能够cover的t-way combination数量
            for val_k in test_case[shuffled_test_case_idx[i]]:  # 遍历每个val
                this_covered_combs_num = 0
                # 下面这行代码计算除了第k个之前的k-1个确定了的值的t-1个组合，即C(k-1,t-1)
                for tm1_comb in itertools.combinations(candidate_row, t - 1):  # 遍历每个t-way combination
                    # 判断t-way comb是否已经被覆盖
                    # 这里使元组有序化，小值总是放在大值前，防止重复

                    # 判断是否已经被cover
                    if tuple(sorted((*tm1_comb, val_k))) not in covered_tway_combination_set:
                        this_covered_combs_num += 1

                # 如果当前选择的val能cover的combination多于之前选的，替换
                if this_covered_combs_num > covered_combs_num:
                    optimal_val = val_k
                    covered_combs_num = this_covered_combs_num

            # k>=t后，每一个新一轮，都有一些新的comb被cover
            candidate_covering_combs_num += covered_combs_num
            if optimal_val == 0:  # 这表明，此时选哪个testcase，都不能创建新的covered conb
                # 此时经过实验，似乎使用随机数是更好的选择
                optimal_val = test_case[shuffled_test_case_idx[i]][random.randint(0, len(test_case[shuffled_test_case_idx[i]]) - 1)]

            candidate_row.append(optimal_val)
            optimal_val = 0

        # 首先按照正确的顺序把选好的covering array candidate排好序,再把排好序的candidate连通其能够cover的comb存储进去
        # 这里使用排好序的candidate连通其能够cover的comb数索引candidate，最后查询时，只需要从这个dict中取最大key，就可以找到candidate
        # 如果有同样的cover数，就会冲突，后者把前者挤掉，但是效果还是一样的
        inverted_candidates_dict[candidate_covering_combs_num] = tuple([candidate_row[shuffled_test_case_idx.index(idx)] for idx in range(k)])
        candidate_covering_combs_num = 0  # 重新赋值
        return max(inverted_candidates_dict.keys())
    '''
    for i in range(k):  # k从0开始，实际上表示k-1
        optimal_val = 0  # 记录每一轮最优的val

        if i + 1 < t:
            
            optimal_val = test_case[shuffled_test_case_idx[i]][random.randint(0, len(test_case[shuffled_test_case_idx[i]]) - 1)]


        else:
            
            covered_combs_num = 0  # 记录最优val能够cover的t-way combination数量
            for val_k in test_case[shuffled_test_case_idx[i]]:  # 遍历每个val
                this_covered_combs_num = 0
                # 下面这行代码计算除了第k个之前的k-1个确定了的值的t-1个组合，即C(k-1,t-1)
                for tm1_comb in itertools.combinations(candidate_row, t - 1):  # 遍历每个t-way combination
                    # 判断t-way comb是否已经被覆盖
                    # 这里使元组有序化，小值总是放在大值前，防止重复

                    # 判断是否已经被cover
                    if tuple(sorted((*tm1_comb, val_k))) not in covered_tway_combination_set:
                        this_covered_combs_num += 1

                # 如果当前选择的val能cover的combination多于之前选的，替换
                if this_covered_combs_num > covered_combs_num:
                    optimal_val = val_k
                    covered_combs_num = this_covered_combs_num
                

            # k>=t后，每一个新一轮，都有一些新的comb被cover
            candidate_covering_combs_num += covered_combs_num
            
        if optimal_val == 0:  # 这表明，此时选哪个testcase，都不能创建新的covered conb
            # 此时经过实验，似乎使用随机数是更好的选择
            optimal_val = test_case[shuffled_test_case_idx[i]][random.randint(0, len(test_case[shuffled_test_case_idx[i]]) - 1)]

        candidate_row.append(optimal_val)  # 选出最优val后，加到candidate里

    # 首先按照正确的顺序把选好的covering array candidate排好序,再把排好序的candidate连通其能够cover的comb存储进去
    # 这里尝试使用了一些优化方法，是否有用需要检验
    # 这里使用排好序的candidate连通其能够cover的comb数索引candidate，最后查询时，只需要从这个dict中取最大key，就可以找到candidate
    # 如果有同样的cover数，就会冲突，后者把前者挤掉，但是效果还是一样的

    # print(shuffled_test_case_idx)
    # print(candidate_row)
    inverted_candidates_dict[candidate_covering_combs_num] = tuple([candidate_row[shuffled_test_case_idx.index(idx)] for idx in range(k)])

    # 此处又是一层优化，C(k,t)是一个covering array能够cover组合的数量的天花板
    # 如果到了天花板，就没必要再往下进行了,直接跳出循环
    if candidate_covering_combs_num == Combination(k, t):
        return candidate_covering_combs_num
    else:
        return 0
    '''


if __name__ == '__main__':
    args = sys.argv
    arg_cnt = len(sys.argv)
    arg_keys = args[1::2]
    arg_vals = args[2::2]

    for i in range(len(arg_keys)):
        if arg_keys[i] == '-t':
            cover_strength = int(arg_vals[i])
        elif arg_keys[i] == '-c':
            candidate_size = int(arg_vals[i])
        elif arg_keys[i] == '-if':
            input_file = arg_vals[i]

    load_test_case_file(input_file)
    if cover_strength > len(test_case):
        print("ERROR!t should be less than k.")
        exit()

    generate_required_tway_num()

    # 读取参数后描述这一过程
    print("this is a CA({}:{},{},{}) problem".format(expected_tway_num, cover_strength, len(test_case), max_val_num))
    AETG(expected_tway_num, cover_strength, len(test_case))
    print("AETG process done,generating {} covering arrays to cover all the combinations.".format(len(AETG_covering_array)))
